package dujiu.leetcode.greed;


import java.util.*;

public class P1481 {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int num : arr) {
            map.put(num,map.getOrDefault(num,0)+1);
        }

        List<Integer> counts = new ArrayList<>(map.values());

        Collections.sort(counts);
        int size = counts.size();

        for (Integer count : counts) {
            if (k >= count) {
                k -= count;
                size--;
            } else {
                break;
            }
        }

        return size;
    }

    public static void main(String[] args) {
        // int[] arr = {5,5,4};
        int[] arr = {4,3,1,1,3,3,2};
        P1481 p = new P1481();
        System.out.println(p.findLeastNumOfUniqueInts(arr, 3));
    }
}
